SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Christofides algorithm</title>

</head>

Christofides algorithm

</h1>

</header>

The Christofides algorithm or Christofides–Serdyukov algorithm is an <a href="Algorithm" title="Algorithm">algorithm</a> for finding approximate solutions to the <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a>, on instances where the distances form a <a href="Metric_space" title="Metric space">metric space</a> (they are symmetric and obey the <a href="Triangle_inequality" title="Triangle inequality">triangle inequality</a>).<a href="#cite_note-gt-1">[1]</a>

It is an <a href="Approximation_algorithm" title="Approximation algorithm">approximation algorithm</a> that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after <a href="Nicos_Christofides" title="Nicos Christofides">Nicos Christofides</a> and Anatoliy Serdyukov (<a href="Russian_language" title="Russian language">Russian</a>: Анатолий Иванович Сердюков). Christofides published the algorithm in 1976; Serdyukov discovered it independently in 1976 but published it in 1978.<a href="#cite_note-cri-2">[2]</a><a href="#cite_note-vabe-3">[3]</a><a href="#cite_note-ser-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

Let G = (V,w) be an instance of the travelling salesman problem. That is, G is a <a href="Complete_graph" title="Complete graph">complete graph</a> on the set V of vertices, and the function w assigns a nonnegative real weight to every edge of G.

According to the triangle inequality, for every three vertices u, v, and x, it should be the case that w(uv) + w(vx) ≥ w(ux).

Then the algorithm can be described in <a href="Pseudocode" title="Pseudocode">pseudocode</a> as follows.<a href="#cite_note-gt-1">[1]</a>

<ol><li>Create a <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> T of G.</li>

<li>Let O be the set of vertices with odd <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a> in T. By the <a href="Handshaking_lemma" title="Handshaking lemma">handshaking lemma</a>, O has an even number of vertices.</li>

<li>Find a minimum-weight <a href="Perfect_matching" title="Perfect matching">perfect matching</a> M in the subgraph <a href="Induced_subgraph" title="Induced subgraph">induced</a> in G by O.</li>

<li>Combine the edges of M and T to form a connected <a href="Multigraph" title="Multigraph">multigraph</a> H in which each vertex has even degree.</li>

<li>Form an <a href="Eulerian_circuit" class="mw-redirect" title="Eulerian circuit">Eulerian circuit</a> in H.</li>

<li>Make the circuit found in previous step into a <a href="Hamiltonian_circuit" class="mw-redirect" title="Hamiltonian circuit">Hamiltonian circuit</a> by skipping repeated vertices (shortcutting).</li></ol>

Steps 5 and 6 do not necessarily yield only a single result; as such, the heuristic can give several different paths.

<div class="mw-heading mw-heading3"><h3 id="Computational_complexity">Computational complexity</h3></div>

The worst-case complexity of the algorithm is dominated by the perfect matching step, which has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3})}</annotation>

</semantics>

</math><img src="./6b04f5c5cfea38f43406d9442387ad28555e2609.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{3})}" loading="lazy"> complexity.<a href="#cite_note-cri-2">[2]</a> Serdyukov's paper claimed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{3}\log n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n^{3}\log n)}</annotation>

</semantics>

</math><img src="./49a0ee6ea4e6d14ebcbfc3029d6d1ad09ca103f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.172ex; height:3.176ex;" alt="{\displaystyle O(n^{3}\log n)}" loading="lazy"> complexity,<a href="#cite_note-ser-4">[4]</a> because the author was only aware of a less efficient perfect matching algorithm.<a href="#cite_note-vabe-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Approximation_ratio">Approximation ratio</h2></div>

The cost of the solution produced by the algorithm is within 3/2 of the optimum.

To prove this, let C be the optimal traveling salesman tour. Removing an edge from C produces a spanning tree, which must have weight at least that of the minimum spanning tree, implying that w(T) ≤ w(C) - lower bound to the cost of the optimal solution.

The algorithm addresses the problem that T is not a tour by identifying all the odd degree vertices in T; since the sum of degrees in any graph is even (by the <a href="Handshaking_lemma" title="Handshaking lemma">handshaking lemma</a>), there is an even number of such vertices. The algorithm finds a minimum-weight perfect matching M among the odd-degree ones.

Next, number the vertices of O in cyclic order around C, and partition C into two sets of paths: the ones in which the first path vertex in cyclic order has an odd number and the ones in which the first path vertex has an even number.

Each set of paths corresponds to a perfect matching of O that matches the two endpoints of each path, and the weight of this matching is at most equal to the weight of the paths. In fact, each path endpoint will be connected to another endpoint, which also has an odd number of visits due to the nature of the tour.

Since these two sets of paths partition the edges of C, one of the two sets has at most half of the weight of C, and thanks to the triangle inequality its corresponding matching has weight that is also at most half the weight of C.

The minimum-weight perfect matching can have no larger weight, so w(M) ≤ w(C)/2.

Adding the weights of T and M gives the weight of the Euler tour, at most 3w(C)/2. Thanks to the triangle inequality, even though the Euler tour might revisit vertices, shortcutting does not increase the weight,

so the weight of the output is also at most 3w(C)/2.<a href="#cite_note-gt-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Lower_bounds">Lower bounds</h2></div>

There exist inputs to the travelling salesman problem that cause the Christofides algorithm to find a solution whose approximation ratio is arbitrarily close to 3/2. One such class of

inputs are formed by a <a href="Path_(graph_theory)" title="Path (graph theory)">path</a> of n vertices, with the path edges having weight 1, together with a set of edges connecting vertices two steps apart in the path with weight 1 + ε

for a number ε chosen close to zero but positive.

All remaining edges of the complete graph have distances given by the <a href="Shortest_path_problem" title="Shortest path problem">shortest paths</a> in this subgraph.

Then the minimum spanning tree will be given by the path, of length n − 1, and the only two odd vertices will be the path endpoints, whose perfect matching consists of a single edge with weight approximately n/2.

The union of the tree and the matching is a cycle, with no possible shortcuts, and with weight approximately 3n/2. However, the optimal solution uses the edges of weight 1 + ε together with two weight-1 edges incident to the endpoints of the path,

and has total weight (1 + ε)(n − 2) + 2, close to n for small values of ε. Hence we obtain an approximation ratio of 3/2.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

<td>Given: complete graph whose edge weights obey the triangle inequality

</td></tr>

<tr>

<td>Calculate <a href="Minimum_spanning_tree" title="Minimum spanning tree">minimum spanning tree</a> T

</td></tr>

<tr>

<td>Calculate the set of vertices O with odd degree in T

</td></tr>

<tr>

<td>Form the subgraph of G using only the vertices of O

</td></tr>

<tr>

<td>Construct a minimum-weight perfect matching M in this subgraph

</td></tr>

<tr>

<td>Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

</td></tr>

<tr>

<td>Calculate Euler tour Here the tour goes A→B→C→A→D→E→A. Equally valid is A→B→C→A→E→D→A.

</td></tr>

<tr>

<td>Remove repeated vertices, giving the algorithm's output. If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A→B→C→E→D→A) if this is an euclidean graph as the route A→B→C→D→E→A has intersecting lines which is proven not to be the shortest route.

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Further_developments">Further developments</h2></div>

This algorithm is no longer the best polynomial time approximation algorithm for the TSP on general metric spaces. Karlin, Klein, and Gharan introduced a <a href="Randomized_algorithm" title="Randomized algorithm">randomized</a> approximation algorithm with approximation ratio 1.5 − 10−36. It follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree.<a href="#cite_note-6">[6]</a><a href="#cite_note-7">[7]</a> The paper received a best paper award at the 2021 <a href="Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a>.<a href="#cite_note-8">[8]</a>

In the special case of <a href="Euclidean_space" title="Euclidean space">Euclidean space</a> of dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">, for any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>0}</annotation>

</semantics>

</math><img src="./2ba126f626d61752f62eaacaf11761a54de4dc84.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>0}" loading="lazy">, there is a polynomial-time algorithm that finds a tour of length at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+{\tfrac {1}{c}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+{\tfrac {1}{c}}}</annotation>

</semantics>

</math><img src="./c47894850701331c520a872d7eb4d05c31777514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.661ex; height:3.343ex;" alt="{\displaystyle 1+{\tfrac {1}{c}}}" loading="lazy"> times the optimal for geometric instances of TSP in

<mrow>

<mrow>

<msup>

<msqrt>

</msqrt>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}</annotation>

</semantics>

</math><img src="./eac3f29d763f875bddeb2c2fa2b60b7aef76f45e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:22.447ex; height:4.843ex;" alt="{\displaystyle O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)}" loading="lazy"> time.</dd></dl>

For each constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> this time bound is in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, so this is called a <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">polynomial-time approximation scheme</a> (PTAS).<a href="#cite_note-9">[9]</a> <a href="Sanjeev_Arora" title="Sanjeev Arora">Sanjeev Arora</a> and <a href="Joseph_S._B._Mitchell" title="Joseph S. B. Mitchell">Joseph S. B. Mitchell</a> were awarded the <a href="G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a> in 2010 for their simultaneous discovery of a PTAS for the Euclidean TSP.

Methods based on the Christofides–Serdyukov algorithm can also be used to approximate the <a href="Stacker_crane_problem" title="Stacker crane problem">stacker crane problem</a>, a generalization of the TSP in which the input consists of ordered pairs of points from a metric space that must be traversed consecutively and in order. For this problem, it achieves an approximation ratio of 9/5.<a href="#cite_note-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGoodrichTamassia2015" class="citation cs2"><a href="Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a> (2015), "18.1.2 The Christofides Approximation Algorithm", Algorithm Design and Applications, Wiley, pp. 513–514</cite>.

</li>

<li id="cite_note-cri-2">^ <a href="#cite_ref-cri_2-0">a</a> <a href="#cite_ref-cri_2-1">b</a> <cite id="CITEREFChristofides1976" class="citation cs2"><a href="Nicos_Christofides" title="Nicos Christofides">Christofides, Nicos</a> (1976), <a rel="nofollow" class="external text" href="https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf">Worst-case analysis of a new heuristic for the travelling salesman problem</a> (PDF), Report 388, Graduate School of Industrial Administration, CMU, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20190721172134/https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf">archived</a> (PDF) from the original on July 21, 2019</cite>

</li>

<li id="cite_note-vabe-3">^ <a href="#cite_ref-vabe_3-0">a</a> <a href="#cite_ref-vabe_3-1">b</a> <cite id="CITEREFvan_BevernSlugina2020" class="citation cs2">van Bevern, René; Slugina, Viktoriia A. (2020), "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem", Historia Mathematica, 53: 118–127, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2004.02437">2004.02437</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.hm.2020.04.003">10.1016/j.hm.2020.04.003</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:214803097">214803097</a></cite>

</li>

<li id="cite_note-ser-4">^ <a href="#cite_ref-ser_4-0">a</a> <a href="#cite_ref-ser_4-1">b</a> <cite id="CITEREFSerdyukov1978" class="citation cs2 cs1-prop-foreign-lang-source">Serdyukov, Anatoliy (1978), <a rel="nofollow" class="external text" href="http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf">"О некоторых экстремальных обходах в графах"</a> [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (Управляемые системы) (in Russian), 17: 76–79</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFBläser2008" class="citation cs2">Bläser, Markus (2008), <a rel="nofollow" class="external text" href="https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA517">"Metric TSP"</a>, in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780387307701</bdi></cite>.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFKarlinKleinGharan2021" class="citation cs2"><a href="Anna_Karlin" title="Anna Karlin">Karlin, Anna R.</a>; Klein, Nathan; Gharan, Shayan Oveis (2021), "A (slightly) improved approximation algorithm for metric TSP", in Khuller, Samir; <a href="Virginia_Vassilevska_Williams" title="Virginia Vassilevska Williams">Vassilevska Williams, Virginia</a> (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, Association for Computing Machinery, pp. 32–45, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2007.01409">2007.01409</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3406325.3451009">10.1145/3406325.3451009</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-8053-9</bdi></cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFKlarreich2020" class="citation cs2"><a href="Erica_Klarreich" title="Erica Klarreich">Klarreich, Erica</a> (8 October 2020), <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/">"Computer Scientists Break Traveling Salesperson Record"</a>, Quanta Magazine, retrieved 2020-10-10</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.sigact.org/prizes/best_paper.html">"ACM SIGACT - STOC Best Paper Award"</a>, www.sigact.org, retrieved 2022-04-20</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFFredericksonHechtKim1978" class="citation cs2">Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (1978), "Approximation algorithms for some routing problems", <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>, 7 (2): 178–193, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0207017">10.1137/0207017</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0489787">0489787</a></cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/christofides.html">NIST Christofides Algorithm Definition</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=Christofides_algorithm&oldid=1300833223">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>